Baraj pentru lotul olimpic, Bucuresti, mai 1997
De ziua lui M.S. (Catalin Francu)
Dificultate: C3-C4

	De ziua lui, M.S. a primit  de la parinti un minunat tort de 
forma cubica. Totusi, desi M.S. se uita cu mult jind la tortul cel siropos,
parintii nu vor sa-l lase sa manance pana nu le easpunde la o intrebare.
Stiind volumul deliciosului tort, M.S. trebuie sa afle latura acestuia.
Se stie ca tortul imbietor are latura numar natural.
	Numele fisierului de intrare se va citi de la tastatura. Acesta nu va
contine decat volumul apetisantului tort, respectiv un numar intreg care nu
depaseste 1000 cifre. datele de intrare sunt corecte.
	Numele fisierului de iesire se citeste de asemenea de la tastatura.
In el se va scrie un singur numar, adica latura calculata a tortului cel gustos.
Exemple: Pentru fisierul de intrare
2097152
fisierul de iesire va contine
128
Pentru fisierul de intrare
10000000000000000000000000000
fisierul de iesire va contine
100000000
Timp limita pentru un test: 10 secunde.
=================================
Solutie (Catalin Francu)
program Tort;
{$B-,I-,R-,S-}
const NMax=1100;
type IntegerVector=array[1..NMax] of Integer;
     Huge=record
            N:Integer;
            D:IntegerVector;
          end;
var V,L:Huge;
    OutName:String;

procedure Atrib(var H:Huge;K:Integer);
{ 0 <= K < 1000 }
begin
  H.D[1]:=K mod 10;
  H.D[2]:=(K div 10) mod 10;
  H.D[3]:=K div 100;
  if K>=100 then H.N:=3 else if K>=10 then H.N:=2 else H.N:=1;
end;

procedure Fill3(var H:Huge);
begin
  while H.N mod 3<>0 do
    begin
      Inc(H.N);
      H.D[H.N]:=0;
    end;
end;

procedure ReadData;
var S:String;
    C:Char;
    i,IAux:Integer;
begin
  Write('Fisierul de intrare: ');ReadLn(S);
  Write('Fisierul de iesire: ');ReadLn(OutName);
  Assign(Input,S);Reset(Input);
  V.N:=0;
  while not Eoln do
    begin
      Inc(V.N);
      Read(C);
      V.D[V.N]:=Ord(C)-48;
    end;
  for i:=1 to V.N div 2 do
    begin
      IAux:=V.D[i];V.D[i]:=V.D[V.N+1-i];V.D[V.N+1-i]:=IAux;
    end;
  Close(Input);
  Fill3(V);
end;

procedure Mul(var A,B,C:Huge);
{ C = A x B }
var i,j,T:Integer;
begin
  C.N:=A.N+B.N-1;
  for i:=1 to C.N+2 do C.D[i]:=0;
  for i:=1 to A.N do
    for j:=1 to B.N do
      C.D[i+j-1]:=C.D[i+j-1]+A.D[i]*B.D[j];
  T:=0;
  for i:=1 to C.N do
    begin
      Inc(C.D[i],T);
      T:=C.D[i] div 10;
      C.D[i]:=C.D[i] mod 10;
    end;
  while T>0 do
    begin
      Inc(C.N);
      C.D[C.N]:=T mod 10;
      T:=T div 10;
    end;
end;

procedure MulCt(K:Integer;var A,B:Huge);
{ B = k * A }
var T,i:Integer;
begin
  B.N:=A.N;
  T:=0;
  for i:=1 to A.N do begin
                       B.D[i]:=k*A.D[i]+T;
                       T:=B.D[i] div 10;
                       B.D[i]:=B.D[i] mod 10;
                     end;
  while T>0 do begin
                 Inc(B.N);
                 B.D[B.N]:=T mod 10;
                 T:=T div 10;
               end;
end;

procedure Add(var A,B,C:Huge);
{ C = A + B }
var i,T,M:Integer;
begin
  if A.N>B.N then begin
                    C.N:=A.N;
                    M:=B.N;
                  end
             else begin
                    C.N:=B.N;
                    M:=A.N;
                  end;
  T:=0;
  for i:=1 to M do
    begin
      C.D[i]:=T;
      C.D[i]:=C.D[i]+A.D[i]+B.D[i];
      T:=C.D[i] div 10;
      C.D[i]:=C.D[i]-10*T;
    end;
  if M=A.N
    then for i:=M+1 to C.N do
           begin
             C.D[i]:=T;
             Inc(C.D[i],B.D[i]);
             T:=C.D[i] div 10;
             C.D[i]:=C.D[i]-10*T;
           end
    else for i:=M+1 to C.N do
           begin
             C.D[i]:=T;
             Inc(C.D[i],A.D[i]);
             T:=C.D[i] div 10;
             C.D[i]:=C.D[i]-10*T;
           end;
  if T>0 then begin
                Inc(C.N);
                C.D[C.N]:=T;
              end;
end;

procedure ShiftR(K:Integer;var A,B:Huge);
{ B =A >> k }
var i:Integer;
begin
  for i:=1 to A.N-K do
    B.D[i]:=A.D[i+K];
  B.N:=A.N-K;
end;

function Sign(var A,B:Huge):Integer;
var i:Integer;
    LA,LB:Integer;
begin
  LA:=A.N;while A.D[LA]=0 do Dec(LA);
  LB:=B.N;while B.D[LB]=0 do Dec(LB);
  if LA>LB
    then Sign:=1
    else if LA<LB
           then Sign:=-1
           else begin
                  i:=LA;
                  while (i>=1) and (A.D[i]=B.D[i]) do Dec(i);
                  if i=0 then Sign:=0
                         else if A.D[i]>B.D[i] then Sign:=1
                                               else Sign:=-1;
                end;
end;

procedure FindRoot;
var i,NewDig:Integer;
    Old2,Old3,A1,A2,A3,A4:Huge;
begin
  Atrib(Old2,0);Atrib(Old3,0);Atrib(L,0);
  for i:=1 to V.N div 3 do
    begin
      ShiftR(V.N-3*i,V,A1);     { A1 = Partea semnif. a lui V }
      NewDig:=10;
      repeat
        Dec(NewDig);
        MulCt(1000,Old3,A2);
        MulCt(300*NewDig,Old2,A3);
        Add(A2,A3,A4);                { A4 = 1000*L^3+300*NewDig*L^2 }
        MulCt(30*NewDig*NewDig,L,A2);
        Add(A2,A4,A3);
        Atrib(A4,NewDig*NewDig*NewDig);
        Add(A3,A4,A2);                { A2 = (10*L+NewDig)^3 ==> Noul Old3 }
      until Sign(A2,A1)<>1;
      MulCt(100,Old2,A1);
      MulCt(20*NewDig,L,A3);
      Add(A1,A3,A4);                  { A4 = (10*L^2+20*L*NewDig }
      Atrib(A3,NewDig*NewDig);
      Add(A4,A3,Old2);
      Old3:=A2;
      MulCt(10,L,A1);L:=A1;L.D[1]:=NewDig;
    end;
end;

procedure WriteRoot;
var i:Integer;
begin
  Assign(Output,OutName);Rewrite(Output);
  for i:=L.N downto 1 do Write(L.D[i]);
  WriteLn;
  Close(Output);
end;

begin
  ReadData;
  FindRoot;
  WriteRoot;
end.
================================

	TESTE
Intrare:
test 1:
7
-----------------------
test 2:
658
-----------------------
test 3:
4573283
-----------------------
test 4:
39723948759278340
-----------------------
test 5:
1234567890123456789012345678901234
-----------------------------
test 6:
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
-----------------------------
test 7:
9082509683408965304865097765820769827359687258967290587692590834762938476987435987345987897289657348763497693476938476983476436579347692471809347010104985713401087143
-----------------------------
test 8:
111111111111111111112222222222222222222233333333333333333333444444444444444444445555555555555555555566666666666666666666777777777777777777778888888888888888888899999999999999999999000000000000000000001111111111111111111122222222222222222222333333333333333333334444444
-----------------------------
test9:
980713490867130976138761376193085769813758961735986071359867918357689135709187981743982379274398724876298620895723478651890402908713408765134876103476108972039487134987123872489657134987631827465871348913468756123076130489761398789617376135689713589671389572476247621947621987198718761536897138713713897138956724876347628763486578595
--------------------------------
test 10:
1000029378401943758091347134013049875013489017368249651839740831130487651348765246981982897621389762138497628976387289726896258762846287624389762476298723948752394875294837534876134987134987213461348097134012304875138475187065187631487561348761348756134897618476134876134861348613486134861987634561849010101384761348876134896134576331
===================================

Iesire:
test 1:
343
--------------------------------
test 2:
284890312
--------------------------------
test 3:
95649836183084656187
--------------------------------
test 4:
62684077522748394364725235511089215485579329704000
--------------------------------
test 5:
1881676372353657772546716040595284158711926247214442805356150338350318185033553256972457279024280904
--------------------------------
test 6:
1371742112482853223593964334705075445816186556927297668038408779149519890260631001371742112482853223552812071330589849108367626886145404663923182441700960219478737997256515775034293552812071330589849108779149519890260631001371742112482853223593964334705075445816186556927297668038408779149519890260631
--------------------------------
test 7:
749234226673868571963096058583402151799384479235902811890565208118614556949742192725771812216713727314619012353681597830285404159183263441205645373132414614949661697892833123550348164368230345368189832827649166722636967188308734687615053842354698703235839452541564772717529286009462669920909687944635660624856194815842892056952371508848550677469415760972410036930230923003977774948022030685496489463276087857355869097420864073913532460038725169587106516308442556429372196412778837716888812588113207
--------------------------------
test 8:
1371742112482853223635116598079561042524828532235939643347064471879286694101509122085048010973936902743484224965706447226337448559670781893497942386831275720170781893004115226337482853223593964334705157750342935528120711659807956104252400508916323731138545952743484208504801097385048010644718792866827160488888888888887448559604938271604920576130864197530864396433460631001371743717421009602194787391906720219478737997331961576406035665295212620192043895747605624144142661179698308641988477366255145226337563786008230467078190288065909463814814826337449218108888889020576138271626337450041152329218347050770919067873802400547231824423593952812073305898556927212620048834019862825253772521262009327844307272702331368998641975302057613827160576131637860088888889300411193415703703705075444170096680384
--------------------------------
test 9:
943249206913093395038006308254096412700158943561375450531521172941313103252696825398648746821959479275545815326820444181249030824771632107760708581728649841469604073054400884272379048116924466686871471761620483272338126202973763700745776946382173776898024650222717593737245662143394600574611839468888951166793134817072064829037869060313190618114083992269408825633241193850502350769055853878192991694501922711699464351891366209317393283566477428259694668860045549295633511860341170023800635609868382222623860326017571998078630467989326899629214967721835730294655069221251052247575412028154290793279500229350784405425833871704263877401006250189058084189235396838346039469889656632504773137387439152357650507702254903669807421679162434613422669085643091119607605552080497484909993683014622226807546291054682513796494602147255511286728000185711604346852871413226350945163408931841925568161042667486919812568508358420668824000528731189519842262548114940137190704086910226759526482688528419830459479994875
--------------------------------
test 10:
1000088137795128132800714433025865793300196172220592158805186838813566624406434240580607311141854179149534006820570954634081451279927677680884957621678590628002631983147862702371713193823697459262686897608205349571494752394306042796961143065417318137315708439617746151318171328988769899171566647533466395842655978544149456836581418833674072438121198733223640925765195856867791233331114113493848184848878542196441040088436643117443637980090386196379145144447229486417168134619034486250348096471197473813032330441061814023163490185452611608154055541553436187270596654885341811062718842465559974846365159768283894922529664575537027412314352530616025118644897878021571932435792654167578762569396374295312767759161263271728417934333660539182159522141267658270049842764859319829503937827183504677685863033743274933290465556533000240848793845626933913524960969904586207933013773160835391571859745689462708055638271791516273347453102201626760740305631232257530207600602548281764818045910487545702054447672691
--------------------------------
